package top.hkyzf.study.leetcode.tree;

import org.junit.Test;

/**
 * @author 朱峰
 * @date 2022-2-22 20:30
 */
public class 二叉搜索树中的插入操作_701 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        return dfs(root, val);
    }

    TreeNode dfs(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val < val) {
            if (root.right == null) {
                root.right = new TreeNode(val);
            } else {
                dfs(root.right, val);
            }
        } else if (root.val > val) {
            if (root.left == null) {
                root.left = new TreeNode(val);
            } else {
                dfs(root.left, val);
            }
        }
        return root;
    }

    @Test
    public void testInsertIntoBST () {
        TreeNode node4 = new TreeNode(3);
        TreeNode node3 = new TreeNode(1);
        TreeNode node2 = new TreeNode(7);
        TreeNode node1 = new TreeNode(2, node3, node4);
        TreeNode root = new TreeNode(4, node1, node2);
        TreeNode node = insertIntoBST(root, 5);
        node.print();
    }
}
